public class Solution {
    /*
     * 交错字符串 n
     * m < n 前m个字符的 i,j并不唯一， 前n个字符的 i,j 唯一哦
     * 前n个字符和前n-1个字符 状态差别就是 一个字符引起的，这个字符可能出自s1(i),也可能出自s2(j)
     * 不想m！想决定状态的 i,j !!!
     *
     * 可以看作是 不同路径 问题
     * 拼接
     *
     * 状态：F(i,j):s1的前i个字符与s2的前j个字符能否组成s3的前i+j个字符
     * 状态转移方程：
     *         F(i,j) = F(i-1,j) && s1[i-1] == s3[i+j-1]
     *         F(i,j) = F(i,j-1) && s2[j-1] == s3[i+j-1]
     * 初始状态：
     *        F(0,0) = true
     *        F(0,j) = F(0,j-1) && s2[j-1] == s3[j-1]
     *        F(i,0) = F(i-1,0) && s1[i-1] == s3[i-1]
     * */
    public static boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int lne3 = s3.length();
        if (len1 + len2 != lne3) {
            return false;
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        char[] chars3 = s3.toCharArray();
        boolean[][] array = new boolean[len1 + 1][len2 + 1];
        array[0][0] = true;
        for (int i = 1; i <= len2; i++) {
            if (chars2[i - 1] == chars3[i - 1]) {
                array[0][i] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= len1; i++) {
            if (chars1[i - 1] == chars3[i - 1]) {
                array[i][0] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                array[i][j] = array[i - 1][j] && chars1[i - 1] == chars3[i + j - 1];
                if (!array[i][j]) {
                    array[i][j] = array[i][j - 1] && chars2[j - 1] == chars3[i + j - 1];
                }
            }
        }
        return array[len1][len2];
    }
}